package 滑动窗口;

import com.alibaba.fastjson.JSON;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class No438找到字符串中所有字母异位词 {

    /**
     * 给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。
     * 字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。
     * 说明：
     * 字母异位词指字母相同，但排列不同的字符串。
     * 不考虑答案输出的顺序。
     * 示例 1:
     * 输入:
     * s: "cbaebabacd" p: "abc"
     * 输出:
     * [0, 6]
     * 解释:
     * 起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
     * 起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。
     */

    public static List<Integer> findAnagrams(String s, String p) {

        Map<Character,Integer> need=new HashMap<>();
        List<Integer> result=new ArrayList<>();
        Map<Character,Integer> window=new HashMap<>();
        //准备好needMap
        for(int i=0;i<p.length();i++){
            need.put(p.charAt(i),need.getOrDefault(p.charAt(i),0)+1);
        }
        int left=0;
        int right=0;
        int valid=0;

        while (left<s.length()){
            /**
             * 1.右指针移动时如何维护
             * 看是否需要更新windowMap,并且维护好valid
             * 2.左指针什么时候移动
             * 当right-left==p.length时
             * 3.左指针移动时怎么维护
             * 看是否要吐出char,吐出前检查valid
             * 4.什么时候更新结果?
             * window吞入后
             */

            if(right<s.length()&&need.containsKey(s.charAt(right))){
                char c=s.charAt(right);
                window.put(c,window.getOrDefault(c,0)+1);
                if(window.get(c).equals(need.get(c))){
                    valid++;
                }
            }
            right++;

            if(valid==need.size())
                result.add(left);

            if(right-left==p.length()){
                char c=s.charAt(left);
                left++;
                if(need.containsKey(c)){
                    if(need.get(c).equals(window.get(c)))
                        valid--;
                    window.put(c,window.get(c)-1);
                }
            }
        }

        return result;
    }

    public static void main(String[] args) {

        String s="abab";
        String p="ab";
        List<Integer> list = findAnagrams(s, p);

        System.out.println(JSON.toJSONString(list));

    }

}
